Packet communication involves a technique of disassembling information at the sending end of a switching network for insertion into separate bursts, or packets, of data and reassembling the same information from the data packets at the receiving end of the network. Communication according to this technique is especially useful in common carrier or time-shared switching systems, since the communication path or circuit required for the packet transmissions is needed only while each packet is being forwarded through the network, and is, therefore, available to other users during intervening periods.
Packet switching offers another attractive feature. That is the flexibility of providing integrated information transport services for a wide range of applications, e.g., interactive data, bulk data, signaling, packetized voice, image, etc. Instead of designing specialized networks optimized for specific forms of applications, many services can be simultaneously operated over the same connection to the network. All varieties of user information are converted into packets, and the network transports these packets between users. End users are not tied to fixed rate connections. Instead, network connections adapt to the particular needs of the end user. Furthermore, it is possible to create a uniform user-network interface applicable to a broad range of services. Note that different applications may require different grades of service from the network. For example, packetized voice transmission has very stringent delay requirements for delivery of associated packets of an ongoing conversation.
Efficient utilization of network resources can be attained by allowing packetized transmissions of a plurality of users on the same connection on a time-shared basis. Thus the packets of one user are interspersed with the packets of other users.
Elements of the resources or facilities which may be shared in such packet networks include transmission link bandwidth (defined as bytes/sec, a measure of link capacity), processor real time (i.e., time immediately available for processing packets), ports or links, and data or packet buffers. In large multinode networks, each node or packet switch accommodates many such ports or links that terminate paths which extend to users' terminal equipments or to other nodes. Each node may include one or more processors for controlling the routing and processing of packets through the node. The node is customarily equipped with a large number of buffers for storing packets prior to such routing or while awaiting an output link. Each line between nodes or extending to users typically serves a plurality of concurrent calls between different terminal equipments. Each packet passing through the network consumes a certain amount of processor real time at each node, takes away a certain amount of link capacity (proportional to the packet size), and occupies buffers while being processed. There is a maximal number of packets per unit of time that a network can accommodate. This notion of "capacity" depends on all the aforementioned resources provisioned within the network, as well as on the particular traffic mix generated by the users.
One problem in a packet switching system arises when many users attempt to utilize the network at the same time. This results in the formation of many paths or circuits for routing the packets and the congestion of the communication facilities. Congestion of a facility is the occurrence of more work than can be handled by the facility in a specific period of time. It has been found that congestion tends to spread through the network if the congestion is uncontrolled. As a result, it is desirable to have a flow/congestion control mechanism for protecting the expected performance level for each service type (e.g., voice) from unpredictable traffic overloads due to other service types. Protection from overload can be provided through the allocation of key network resources. In the event that a key resource is overloaded by traffic, it is desirable that the overall performance of the system should degrade as gracefully as possible. Controlling the utilization of the key resource may require different objectives under the overload condition than under a normal load condition.
A principal area of packet congestion is in buffers, or queues, in each node, particularly where the buffers become unavailable to store incoming packets. Yet the buffer requirement is closely related to the utilization of processor real time and/or link bandwidth. When the processor real time is exhausting, or when the link bandwidth is not sufficient to handle the packet traffic, queues within the switching node will build up causing a long delay. Finally packet buffers will be exhausted, resulting in the dropping of packets. A number of flow control procedures, e.g., end-to-end windowing, have been developed and commercially exploited for controlling congestion.
The known end-to-end windowing scheme for flow control is advantageous when network operation is viewed strictly from the network periphery. Each machine can have many logical channels simultaneously established between itself and various other machines. For each of these logical channels, a given machine is allowed to have W unacknowledged packets outstanding in the network. For example, a machine can initially transmit W packets into the network as fast as it desires; but, thereafter, it must wait until it has received an acknowledgment from the destination machine for at least one of those outstanding packets before it can transmit more packets.
This very scheme has several very desirable properties. There is very little wasted link bandwidth caused by the flow-controlling mechanism, because the number of bits in an acknowledgment can be made very small compared to the numbe of bits in the W packets to which it refers. There is an automatic throttling of transmission under a heavy load condition, because the increased round-trip delay will slow down the acknowledgments and hence the traffic source.
There also are disadvantages to the end-to-end window flow control. The windowing mechanism by itself is not robust enough. The mechanism relies upon the end user adhering to an agreed-upon window size. By unilaterally increasing its window size, an abusive user can get favorable performance while degrading the performance for other users. Even if all users obey their specified end-to-end window sizes, it is very difficult to determine suitable window sizes for various load conditions. In general, the window size W is chosen large enough to allow uninterrupted transmission when the network is lightly loaded; however, overload conditions may require an unacceptably large amount of buffer storage within the packet switch. It is possible for end users to adaptively adjust their window sizes based on network congestion, but this by itself would not necessarily give a fair congestion control.
Another drawback to relying upon the end-to-end windowing mechanism is that not all agreed-upon user applications are subject to window-based end-to-end control. For example, the Unnumbered Information (UI) transfer embedded in some window-based protocols, e.g., LAPD, allows the end users to send packets without any windowing limitation. Other examples are packetized voice or packetized voice-band data applications where an end-to-end window is not applicable.
It has been proposed that in an integrated voice of data packet network the proper way to control flow or congestion is by allocating bandwidth to connections and by making new connections only when the needed bandwidth is available.
This means that the network must provide a mechanism for users to select their bandwidth needs and indicate the burstiness of their transmissions. Thereafter, the network must enforce those parameters with respect to the respective users.
A key part of bandwidth allocation is the mechanism used to select and specify the needed bandwidth and to limit users to their selections. Perhaps the simplest approach is the so-called "leaky bucket" method. A count in a counter, associated with each user terminal transmitting on a connection, is incremented whenever the user sends a packet and is decremented periodically. The user selects the rate at which the count is decremented (this determines the average bandwidth) and the value of a threshold (a number indicating burstiness). If the count exceeds the threshold upon being incremented, the network discards that packet.
There are problems with this "leaky bucket" bandwidth allocation proposal. A major problem is the fact that the control is open-loop in nature. A user's packets will be dropped once the threshold is exceeded even when the network could have handled the packets. Precious network resources would be wasted. The unnecessary throttling of that user's data may sustain the information transfer over a lengthy period, contributing to network congestion at a later time. Another problem is that the limiting network resource may be processor real time rather than link bandwidth.